package LinkedList;

//约瑟夫对象
public class JosephCircular {
    //总人数
    private int count;
    //被杀死的人间隔的位数
    private int step;
    //设置一个双向循环链表
    private PersonDoubleCircularLinkedList personDoubleCircularLinkedList;

    public JosephCircular(int count, int step)
    {
        this.count = count;
        this.step = step;
        this.personDoubleCircularLinkedList = new PersonDoubleCircularLinkedList();
        for (int i = 1; i <= count; i++) {
            personDoubleCircularLinkedList.add();
        }
    }

    /**
     * 执行约瑟夫环的模拟代码
     *
     * @return void
     **/
    public void run()
    {
        if (this.personDoubleCircularLinkedList.count() < 2) {
            System.out.println("最后一个被杀者" + this.personDoubleCircularLinkedList.getCurrentPointerIndex());
            return;
        }
        for (int i = 1; i < this.step; i++) {
            this.personDoubleCircularLinkedList.movePointer();
        }
        System.out.printf("第%d个人被杀死\n", this.personDoubleCircularLinkedList.getCurrentPointerIndex());
        this.personDoubleCircularLinkedList.deleteMovePointer();
        this.run();
    }

    //人的双向链表(这是一个单向循环链表)
    class PersonDoubleCircularLinkedList {
        //指针结点
        private JosephCircular.PersonDoubleCircularLinkedList.Node pointer = null;

        /**
         * 增加一个人
         *
         * @return void
         **/
        public void add()
        {
            if (null == this.pointer) {
                JosephCircular.PersonDoubleCircularLinkedList.Node newNode = new JosephCircular.PersonDoubleCircularLinkedList.Node();
                newNode.setIndex(1);
                this.pointer = newNode;
                this.pointer.setNext(this.pointer);
                this.pointer.setPrev(this.pointer);
                return;
            }

            JosephCircular.PersonDoubleCircularLinkedList.Node lastNode = this.pointer;
            while (this.pointer != lastNode.getNext()) {
                lastNode = lastNode.getNext();
            }
            JosephCircular.PersonDoubleCircularLinkedList.Node newNode = new JosephCircular.PersonDoubleCircularLinkedList.Node();
            int index = lastNode.getIndex() + 1;
            newNode.setIndex(index);
            newNode.setNext(lastNode.getNext());
            newNode.setPrev(lastNode);
            lastNode.getNext().setPrev(newNode);
            lastNode.setNext(newNode);
        }

        /**
         * 移动指针
         *
         * @return void
         **/
        public void movePointer()
        {
            if (null != this.pointer) {
                this.pointer = this.pointer.getNext();
            }
        }

        /**
         * 删除当前指针的结点并移动指针
         *
         * @return void
         **/
        public void deleteMovePointer()
        {
            if (this.count() > 1) {
                this.pointer.getPrev().setNext(this.pointer.getNext());
                this.pointer.getNext().setPrev(this.pointer.getPrev());
                this.pointer = this.pointer.getNext();
            } else {
                this.pointer = null;
            }
        }

        /**
         * 获取当前链表中结点的数量
         *
         * @return int
         **/
        public int count()
        {
            if (null == this.pointer) {
                return 0;
            }
            JosephCircular.PersonDoubleCircularLinkedList.Node lastNode = this.pointer;
            int count = 1;
            while (this.pointer != lastNode.getNext()) {
                lastNode = lastNode.getNext();
                count++;
            }
            return count;
        }

        /**
         * 获取当前节点的人员序号
         *
         * @return int
         **/
        public int getCurrentPointerIndex()
        {
            if (null == this.pointer) {
                return -1;
            }
            return this.pointer.getIndex();
        }

        class Node {
            //下一个结点
            private JosephCircular.PersonDoubleCircularLinkedList.Node next = null;
            //上一个结点
            private JosephCircular.PersonDoubleCircularLinkedList.Node prev = null;
            //人的序号
            private int index;

            public Node getNext()
            {
                return next;
            }

            public void setNext(Node next)
            {
                this.next = next;
            }

            public int getIndex()
            {
                return index;
            }

            public void setIndex(int index)
            {
                this.index = index;
            }

            public Node getPrev()
            {
                return prev;
            }

            public void setPrev(Node prev)
            {
                this.prev = prev;
            }
        }
    }
}
